//
// Created by guanyicheng on 2022/6/6.
//

#include "../../common.h"

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode *root) {

        if (root->left == root->right) return true;
        if (root->left == nullptr || root->right == nullptr) return false;

        deque<TreeNode*> dp{};
        dp.emplace_back(root->left);
        dp.emplace_back(root->right);

        while (!dp.empty()) {
            auto a = dp.front();
            dp.pop_front();
            auto b = dp.front();
            dp.pop_front();
            if (a->val != b->val) return false;
            if (a->left != nullptr && b->right != nullptr) {
                dp.emplace_back(a->left);
                dp.emplace_back(b->right);
            } else if (a->left != b->right) {
                return false;
            }
            if (a->right != nullptr && b->left != nullptr) {
                dp.emplace_back(a->right);
                dp.emplace_back(b->left);
            } else if(a->right != b->left) {
                return false;
            }
        }
        return true;
    }
};